1. Field of the Invention
The present invention relates to a fast binary reduction tree for reducing the number of partial product levels associated with high speed multiplication circuits.
2. Description of Related Art
State of the art high speed multiplication circuits multiply an n bit multiplier and an m bit multiplicand by simultaneously generating n partial product terms, which are reduced to a final product by adding the partial products. Of these two sequences--the formation of partial product terms and the summation thereof--summation is the one that limits the computer computational speed. Summation is done by creating levels of summation, with all summations at a given level being done in parallel. Thus, the total delay of the multiplication is the number of levels times the delay at each level. The primary goal of the technology is to reduce the number of levels, without significantly increasing the delay at each level.
Traditionally, trees of carry save adders (CSAs) are used to sum partial products. Each m bit CSA is made up of m full adders and takes as inputs three m bit integers A=a.sub.m-1, a.sub.m-2, . . . , a.sub.o ; B=b.sub.m-1, b.sub.m-2. . . , b.sub.o ; and C=c.sub.m-1, c.sub.m-2, . . . , c.sub.o and produces two integer outputs S1=S1.sub.m-1, S1.sub.m-2, . . . , s1.sub.0 and S2=s2.sub.m, s2.sub.m-2, . . . , s2.sub.0. To illustrate, a four bit CSA is shown in FIG. 1 (m=4) and designated there by the general reference numeral 10. In accordance with the just-discussed characteristic organization, the four bit CSA 10 is made up of four full adders and takes three 4 bit integers A=a.sub.3, a.sub.2, a.sub.1, a.sub.0 ; B=b.sub.3, b.sub.2, b.sub.1, b.sub.0 and C=C.sub.3, C.sub.2, C.sub.1, c.sub.0 as inputs and produces as outputs the two integers S1=s1=s1.sub.3, s1.sub.2, s1.sub.1, s1.sub.0 and S2=s2.sub.4, s2.sub.3, s2.sub.2, s2.sub.1, s2.sub.0.
FIG. 2 depicts a block diagram equivalent of an arbitrary width carry save adder 10.
FIG. 3 schematically depicts an exemplary carry save adder tree 15 for six partial products. In general, such carry save adder trees reduce n partial products to 2 in 0(log.sub.3/2 n) levels. Assuming that P.sub.i is the number of partial products to be reduced in level i of a carry save adder tree, each level of CSAs will reduce P.sub.i partial products to P.sub.i+1 =2x P.sub.i /3 +(P.sub.i mod 3) partial products using ( P.sub.i /3 CSAs. At the level at which the number of partial products is reduced to 2, a carry propagate adder (CPA) is used to compute the final sum. Thus, in the illustrative carry save adder tree 15, six partial products (P.sub.0 =6) are reduced to two partial products in the sequence P.sub.1 =4, P.sub.2 =3 and P.sub.3 =2 using three levels of CSAs 10.sub.1 -10.sub.4 and, at the last level, a carry propagate adder 16 is used to compute the final sum.